package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/10 13:25
 * <p>
 * 功能描述:
 */
public class _0098 {

    public static void main(String[] args) {
        _0098 test = new _0098();

        TreeNode root = new TreeNode(10);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(15);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(20);
        TreeNode node5 = new TreeNode(17);
        TreeNode node6 = new TreeNode(22);

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node4.right = node6;
        test.isValidBST2(root);
    }



    /*-------------------------------------正确的递归法-----------------------------------------*/
    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null)
            return true;

        int val = node.val;
        if (lower != null && val <= lower)
            return false;
        if (upper != null && val >= upper)
            return false;

        if (! helper(node.right, val, upper))
            return false;
        if (! helper(node.left, lower, val))
            return false;
        return true;
    }

    public boolean isValidBST2(TreeNode root) {

        return helper(root, null, null);
    }
    /*----------------------------------------------------------------------------------------*/


    /*---------------------------------------错误方法-------------------------------------------*/
    /**
     * 示例 2:
     * <p>
     * 输入:
     *        10
     *       /  \
     *      5    15
     *     / \  / \
     *         6  20
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。
     *
     * 下面方法错误的原因:
     * 问题是，这种方法并不总是正确。不仅右子结点要大于该节点，整个右子树的元素都应该大于该节点。
     * https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode/
     */


    int value;  //这里记录了，不知道为什么还是错的。原因是不能只记录root节点的，每一个子树的父节点都应该记录
    public boolean isValidBST1(TreeNode root) {
        if (root == null)
            return true;
        value = root.val;
        boolean result = recurIsBst(root, new TreeNode(root.val + 1), 0);
        return result;
    }

    //左子树是0，右子树是1
    public boolean recurIsBst(TreeNode cur, TreeNode pre, Integer flag) {
        if (cur == null)
            return true;
        if (flag == 0) {
            if (cur.val >= pre.val || cur.val >= value)
                return false;
        }
        if (flag == 1) {
            if (cur.val <= pre.val || cur.val <= value)
                return false;
        }

        boolean left = recurIsBst(cur.left, cur, 0);
        boolean right = recurIsBst(cur.right, cur, 1);

        if (left && right)
            return true;

        return false;
    }

    /*----------------------------------------------------------------------------------------*/
}
